A computer system typically includes a memory hierarchary for data storage and retrieval. The memory hierarchary includes one or more caches and system memory. The computer system tracks data stored in the caches using a mapping function, such as a direct mapping, a set-associative mapping, or a fully-associative mapping.
In a direct-mapped cache, each address in main memory has one place in the cache for which it may be stored. In a set-associative mapped cache, each address in main memory has a particular number of places in the cache for which it may be stored. This is also referred to as an “n-way” associative mapped cache, where “n” is the number of places that a particular address in main memory may be stored in cache. In a fully-associative mapped cache, any address in main memory may map to any address in the cache. The direct mapped cache is typically the fastest but least flexible approach, and the fully-associative mapped cache is the most flexible but slowest approach.